home *** CD-ROM | disk | FTP | other *** search
- Path: nntp.teleport.com!usenet
- From: GHouck <hksys@teleport.com>
- Newsgroups: comp.lang.c
- Subject: Re: bubble sort walkthrough needed, please
- Date: 19 Apr 1996 04:55:25 GMT
- Organization: systems hk
- Message-ID: <4l76bt$t4h@nadine.teleport.com>
- References: <4l39b4$s2h@coranto.ucs.mun.ca>
- NNTP-Posting-Host: ip-pdx20-13.teleport.com
- Mime-Version: 1.0
- Content-Type: text/plain; charset=us-ascii
- Content-Transfer-Encoding: 7bit
- X-Mailer: Mozilla 1.22 (Windows; I; 32bit)
-
- jdeeley@calvin.stemnet.nf.ca (J.Deeley) wrote:
- >
- >I am trying to understand how this bubble sort is working. I understand
- [snip]
- >that I can't fathom. I've been working at this ever since last night and
- >I still don't get it. Could someone tell me what is going on in that
- >part?
- >main ()
- >{
- > int item[100];
- > int a, b, t;
- > int count;
- >
- > /* read in numbers */
- > printf("How many numbers? ");
- > scanf("%d", &count);
- > for (a=0; a<count; a++) scanf("%d", &item[a]);
- >
- > /* now sort them using a bubble sort */
- > for(a=1; a<count; a++)
- > for(b=count-1; b>=a;--b) {
- > /* compare the adjacent elements */
- > if(item [b-1] > item [b]) {
- > /* exchange elements */
- > t = item [b-1];
- > item[b-1] = item [b];
- > item [b] = t;
- > }
- > }
- >
- JD
- It doesn't look exactly like the one I am vaguely familiar with, however, it
- appears to be doing this:
-
- 1. The outer (a) loop provides the inner (b) loop with an ending value, starting
- at 1, incrementing to the (count-1).
- 2. The inner loop then sequences backward from the end of the array,
- comparing (and swapping) adjacent elements if they are not in ascending order.
- 3. The inner loop completes when the value of (b) is less than the value of (a).
- 4. The outer (a) loop then increments, reducing the range that the inner (b) has
- to iterate.
-
- This is supposed to float (bubble) the smaller values to the top; however, I have
- always seen it with the inner loop index increasing rather than decreasing in value. The
- bubble sort, once you figure it out, is handy for small, quick and dirty sorts, where
- the effort to implement something more complex (and perhaps more efficient) is just not
- worth it. Once you get over a score of elements in the array, the n^2 time it takes starts
- to become prohibitive.
-
- Yours,
-
- Geoff Houck
- systems hk
-
-
-
-